/*
 * Copyright 2010-2012 Susanta Tewari. <freecode4susant@users.sourceforge.net>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package commons.util.graph;

import com.google.common.base.Function;

import commons.util.ExceptionUtil;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Defines an ordered n-ary (variable) subtree. Data types are assumed to be immutable.
 *
 * @param <N> node data type
 * @param <E> edge data type
 * @author Susanta Tewari
 */
public final class Node<N, E> {

    /** Field description */
    private final Node<N, E> parent;

    /** Field description */
    private N data;

    /** Field description */
    private List<Node<N, E>> children;

    // edges to the children

    /** Field description */
    private List<Edge<N, E>> edges;

    /**
     * Creates a node that can have a variable number of children. Note that {@code childrenCapacity}
     * is only an estimate (to boost performance), the actual number of children the node contains
     * can be different.
     *
     * @param parent the parent node of this node or {@code null} if this node is to be a root node
     * @param data node data
     * @param childrenCapacity an estimate of the number of potential children
     */
    public Node(Node<N, E> parent, N data, int childrenCapacity) {

        if (data == null) {
            ExceptionUtil.throwIllegalArgExNull("data");
        }

        this.parent   = parent;

        this.data     = data;

        this.children = new ArrayList<>(childrenCapacity);

        this.edges    = new ArrayList<>(childrenCapacity);
    }

    /**
     * A copy factory method. The given functions can be used to transform the node and edge data
     * types.
     *
     * @param <N1> node data type of the source tree
     * @param <N2> node data type of the tree created
     * @param <E1> edge data type of the source tree
     * @param <E2> edge data type of the tree created
     * @param src source tree to be copied
     * @param nodeFunction transform node data from {@code N1} to {@code N2}
     * @param edgeFunction transform edge data from {@code E1} to {@code E2
     * @return
     */
    public static <N1, N2, E1, E2> Node<N2, E2> transform(Node<N1, E1> src,
            Function<N1, N2> nodeFunction, Function<E1, E2> edgeFunction) {

        Node<N2, E2> result = new Node<>(null, nodeFunction.apply(src.getData()),
                                         src.getChildrenCount());

        copy(src, result, nodeFunction, edgeFunction);

        return result;
    }


    /**
     * Method description
     *
     *
     * @param src
     * @param dest
     * @param nodeFunction
     * @param edgeFunction
     * @param <N1>
     * @param <N2>
     * @param <E1>
     * @param <E2>
     */
    private static <N1, N2, E1, E2> void copy(Node<N1, E1> src, Node<N2, E2> dest,
            Function<N1, N2> nodeFunction, Function<E1, E2> edgeFunction) {

        for (Node<N1, E1> srcChildNode : src.getChildren()) {

            Edge<N1, E1> edge          = src.getChildEdge(srcChildNode);

            Node<N2, E2> destChildNode = dest.addChild(nodeFunction.apply(srcChildNode.getData()),
                                             edgeFunction.apply(edge.getData()),
                                             srcChildNode.getChildrenCount());

            if (!srcChildNode.isLeaf()) {

                copy(srcChildNode, destChildNode, nodeFunction, edgeFunction);
            }

        }
    }


    /**
     * It creates a new child node and connects it with a new edge.
     *
     * @param childNodeData data of the new child node
     * @param edgeData data of the new edge
     * @param childrenCapacity
     * @return the newly created child node
     */
    public Node<N, E> addChild(N childNodeData, E edgeData, int childrenCapacity) {

        if (childNodeData == null) {
            ExceptionUtil.throwIllegalArgExNull("childNodeData");
        }

        if (edgeData == null) {
            ExceptionUtil.throwIllegalArgExNull("edgeData");
        }

        Node<N, E> child = new Node<>(this, childNodeData, childrenCapacity);

        children.add(child);

        edges.add(new Edge<>(this, child, edgeData));

        return child;
    }


    /**
     * Removes the given child from this node and its associated edge.
     *
     * @param child child to be removed
     * <li>{@code child} is {@code null}</li>
     * <li>{@code child} is not found</li>
     * </ol>
     */
    public void removeChild(Node<N, E> child) {

        // check param child
        checkChildParam(child);

        edges.remove(getChildEdge(child));

        children.remove(child);
    }


    /**
     * Returns the edge associated with the specified child.
     *
     * @param child a child of this node
     * @return the edge associated with the child
     * <li>{@code child} is {@code null}</li>
     * <li>{@code child} is not found</li>
     * </ol>
     */
    public Edge<N, E> getChildEdge(Node<N, E> child) {

        // check param child
        checkChildParam(child);

        // find edge
        for (Edge<N, E> edge : edges) {

            if ((edge.getChild() == child) && (edge.getParent() == this)) {

                return edge;
            }
        }

        // child present but edge absent!
        throw ExceptionUtil.throwIllegalStateEx(getClass(), "Child_Has_No_Edge", child.getData());

    }


    /**
     * Finds the ordered (entry order) leaf nodes of this subtree.
     *
     * @return the ordered (entry order) leaf nodes
     */
    public List<Node<N, E>> getLeafs() {

        @SuppressWarnings("CollectionWithoutInitialCapacity") List<Node<N, E>> result =
            new ArrayList<>();

        if (isLeaf()) {

            result.add(this);

            return result;
        }

        for (Node<N, E> child : children) {

            if (child.isLeaf()) {

                result.add(child);


            } else {
                result.addAll(child.getLeafs());
            }
        }

        return result;
    }


    /**
     * Checks if the child in the argument is present
     *
     * @param child a child in the argument of any non-private method of this class
     * <li>{@code child} is {@code null}</li>
     * <li>{@code child} is not found</li>
     * </ol>
     */
    private void checkChildParam(Node<N, E> child) {

        // child null ?
        if (child == null) {
            ExceptionUtil.throwIllegalArgExNull("child");
        }


        // child present ?
        if (!children.contains(child)) {
            ExceptionUtil.throwIllegalArgEx(getClass(), "ChildNode_Not_Found", child.getData());
        }
    }


    /**
     * Finds the first node under this subtree that has the given data (based on {@code equals()}).
     *
     * @param data data of the searched node
     * @return the first node with the given label or {@code null} if none is found
     */
    public Node<N, E> findFirstNode(N data) {

        if (data == null) {
            ExceptionUtil.throwIllegalArgExNull("data");
        }

        if (data.equals(data)) {
            return this;
        }

        for (Node<N, E> node : children) {

            Node<N, E> result = node.findFirstNode(data);

            if (result != null) {
                return result;
            }
        }

        return null;
    }


    /**
     * Finds the first edge under subtree that has the given data (based on {@code equals()}).
     *
     * @param data data of the searched edge
     * @return the first edge with the given label or {@code null} if none is found
     */
    public Edge<N, E> findFirstEdge(E data) {

        if (data == null) {
            ExceptionUtil.throwIllegalArgExNull("data");
        }

        for (Edge<N, E> edge : edges) {

            if (edge.getData().equals(data)) {

                return edge;
            }
        }

        for (Node<N, E> node : children) {

            Edge<N, E> result = node.findFirstEdge(data);

            if (result != null) {
                return result;
            }
        }

        return null;
    }


    /**
     * The data associated with this node. Node Data types are assumed to be immutable.
     *
     * @return node data
     */
    public N getData() {

        return data;
    }


    /**
     * The data associated with this node. Node Data types are assumed to be immutable.
     *
     * @param data node data
     */
    public void setData(N data) {

        this.data = data;
    }


    /**
     * A rad-only view of the children of this node.
     *
     * @return children of this node
     */
    public List<Node<N, E>> getChildren() {

        return Collections.unmodifiableList(children);
    }


    /**
     * The total number of children directly under this node.
     *
     * @return children count
     */
    public int getChildrenCount() {

        return children.size();
    }


    /**
     * Checks if this node is a root.
     *
     * @return {@code true} if this node is the root; {@code false} otherwise
     */
    public boolean isRoot() {

        return parent == null;
    }


    /**
     * Checks if this node is a leaf.
     *
     * @return @return {@code true} if this node is the leaf; {@code false} otherwise
     */
    public boolean isLeaf() {

        return children.isEmpty();
    }


    /**
     * The parent node of this node. The root node has {@code null} parent.
     *
     * @return the parent node of this node
     */
    public Node<N, E> getParent() {

        return parent;
    }


    /**
     * {@code toString()} on its data.
     *
     * @return {@code toString()} on its data
     */
    @Override
    public String toString() {

        return data.toString();
    }
}
